#include<iostream>
#include<map>
#include<cstring>
#include<stdio.h>
#include<cstdlib>

using namespace std;

int main()
{
    int k,p,n,res;
    map<int,int> m;
    map<int,int> :: iterator it;
    while( scanf("%d",&n) )    
    {
        if(n==0)            
        {
            break;                    
        }
        else if(n==1)
        {
            scanf("%d%d",&k,&p);
            m[p] = k; 
            continue;       
        }
        else if(n==2)
        {
            if(m.size()==0)
            {               
                printf("0\n");
            }
            else
            {
                it = m.end();
                it--;
                printf("%d\n",it->second);
                m.erase(it->first);
            }
        }
        else
        {
            if( m.size()==0 )
            {             
                printf("0\n");
            }
            else
            {
                it = m.begin();
                printf("%d\n",it->second);
                m.erase(it->first);    
            }
        }
    }//while
    
    system("pause");
    return 0;
} 
